1. Field
This application relates to network elements and, more particularly, to a method and apparatus for implementing filter rules in a network element.
2. Description of the Related Art
Data communication networks may include many switches, routers, and other devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units, such as frames, packets, cells, or segments, between the network elements by utilizing one or more communication links. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
FIG. 1 illustrates one example of a communication network 10. As illustrated in FIG. 1, customer equipment 12 enables subscribers to access the network 10 by interfacing with one or more Provider Edge (PE) network elements 14. The provider edge network elements collect traffic from multiple subscribers and multiplex the traffic onto the network backbone, which includes multiple Provider (P) network elements 16 connected together. The subscribers thus may obtain access to the network 10 to exchange data with other subscribers, to obtain access to networked resources, or otherwise to take advantage of the communication services provided by the communication network.
The network elements on the communication network, such as customer equipment 12, provider edge network elements 14, and provider network elements 16, communicate with each other using predefined sets of rules, referred to herein as protocols. Multiple protocols exist, and are used to define aspects of how the communication network should behave, such as how the network elements should identify each other on the network, the format that the data should take in transit, and how the information should be reconstructed once it reaches its final destination. Examples of several protocols include Asynchronous Transfer Mode (ATM), Frame Relay (FR), Ethernet, Transport Control Protocol (TCP), Internet Protocol (IP), Point-to-Point Protocol (PPP), and Multi-Protocol Label Switching (MPLS), although there are probably more than 100 other protocols as well that may be used to govern aspects of communications taking place over the network.
The network 10 may be shared by many subscribers. To enable the network elements to identify packets associated with particular subscribers or that require special attention, filter rules may be specified indicating that particular actions should be taken on packets with particular attributes. The filtering rules allow the network administrator to specify how the packets should be identified and to specify a particular action to be taken on packets matching the attributes specified in the filter rules. For example, priority, quality of service, blocking, and other actions all use filters to identify packets for special treatment by the network elements.
Different filter rules may need to be applied to different interfaces that have been created on each network element. Interfaces may be physical, such as related to particular ports, or may be logical and span multiple ports. An example of a logical interface that may not be permanently associated with a particular physical port is a Virtual Local Area Network (VLAN), in which traffic for the VLAN may arrive at the network element over more than one port. To enable different filter rules to be applied to different flows of traffic, an Access Control List (ACL) is created for each port or VLAN on which filtering is to be implemented. The Access Control List contains a group of filter definitions referred to herein as Access Control Entries (ACE). The ACEs may be created using an Access Control Template (ACT) that is associated with the ACL. The ACT defines the format of the ACEs, such as which fields may be used to specify particular attributes, the order of the fields, and the format of the fields. All ACEs in a given ACL are created using the same ACT so that all of the ACEs in the ACL are formatted in a common manner. Different ACTs may be used for different ACLs on the same network element, however.
Filter rules (ACEs) may be defined by the network administrator or may be defined by programs running on the network element. Accordingly, there may be multiple ACEs within an ACL that all specify different actions to be performed on a particular group of packets having particular attributes.
Conventionally, only one ACE from a given ACL would be located and applied to a packet when the packet was received at the network element. For example, when a packet was received, the ACL for the port/VLAN on which the packet was received would be searched to determine if the packet matched an ACE within the ACL. If so, the first ACE to be located was applied and the action associated with that ACE would be applied to the packet.
Recognizing that more than one ACE within an ACL may apply to a given packet, a system was developed that enabled multiple ACEs to be retrieved sequentially from a given ACL. Specifically, using this sequential retrieval process, when a packet was received, the appropriate ACL for that packet would be searched to locate a first ACE. That ACE was then removed from the ACL and the ACL would be searched a second time. If a second matching ACE was located, the second ACE would be removed from the ACL and the process would iterate until a desired number of ACEs were identified. A prioritizing process was then used to identify which of the actions from the located ACEs should be applied to the packet.
While this solution may enable multiple ACEs to be identified and applied to a given packet, it requires multiple searches to be performed within the ACL. This increases the processing time associated with performing a filter search for each packet, which is undesirable when the network element is required to have very fast throughput. Additionally, since the process requires multiple searches to be performed, there is a practical limit to the number of ACEs that may be identified using this process. For example, the network element may not have sufficient time to perform more than around five search sequences for a given packet so that only up to five ACEs may be identified for a given packet. Thus, potentially other ACEs also relevant to the packet may be not located and thus not applied by this process. Accordingly, it would be advantageous to provide another method and apparatus for determining which ACE actions should be applied to a given packet.